Data bases fall into four general types or classes. A first type, which can be called a hierarchical data base, is modeled on a tree format. Objects, i.e., items of information, in the data base are related to more fundamental items much as leaves are related to branches and branches are related to the trunk tree. This form of data base emphasizes the superior-inferior relationships between data items and is very suitable for data in which such relationships are inherent, e.g., organization charts.
Another type of data base takes on a network form which can be molded as a directed graph. The data items (graph nodes or vertices) in the network are all of equal weight or value and are interconnected by relational properties symbolized by the directed edges of the graph. This form of data base organization is suitable for data items which have multiple hierarchical relationships, e.g., inventory items linked together by common supplier and common warehouse.
A third form of data base is modeled on the relational properties of data items. In such a data base, each relationship is a table with each row listing one of the objects sharing the specific relationship. Virtually all of the information in such a relational data base constitutes the relationships between objects, rather than the objects themselves.
A fourth kind of data base model has been called the entity-relationship model. In this model, which can also be represented by a directed graph, the data entities constitute the vertices of the graph while the directed edges of the graph represent relationships between the entities' nodes. Typically, a data record is a node including both the data item itself and pointers to other data records. The pointers are used to represent the edges of the graph, i.e., the relationships between vertices (data items). Such pointers include an identification of the entity or node pointed to as well as some indication of the nature of the relationship to that other node. Again, the entity-relationship model is suitable for some forms of data in which data entities and relationships between those data entities are inherent in the real world situation being modeled. Some authorities maintain that the entity-relationship model is generic and that the other three models are special cases of the identity-relationship model. The present invention is concerned with the latter type of data base, i.e., entity-relationship data bases. One such data base is described in "An Entity-based Database User Interface" by R. G. G. Cattell, 1980 Proc. ACM-SIGMOD 144, International Conference on Management of Data, Santa Monica, Calif., May 14-16, 1980.
Although single relationships between two objects are common and can be well represented by a directed graph model, some types of relationships inherently involve more than two entities. For example, a relationship such as "parents of" involves a child and two parents. The "parents of" relationship is not fully defined without two (both) parents. Although the relationship between the parent may be simple (e.g., married), such a relationship is not essential to the "parents of" relationship, which involve three persons, father, mother and child. In graph theory, the parenthood edge is called called a hyperedge, since it points simultaneously to more than one vertex. Hypergraphs and hyperedges are discussed in greater detail in a text by C. Berge entitled "Graphs and Hypergraphs", North Holland Company, New York 1973, particularly at pages 389-413.
Since many real world situations involve multiple relationships between data objects, the hypergraph model is eminently suitable for representing data concerning many real world situations. Unfortunately, it has heretofore been difficult or impossible to represent such data bases in a form which is readily processed and efficiently utilized by digital computers.